import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
class Info{
    boolean isSameVal;
    boolean isSane;
    public Info(boolean v,boolean i){
        this.isSameVal = v;
        this.isSane = i;
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class TextDemo {
    public Info ans(TreeNode leftNode,TreeNode rightNode){
        if(leftNode==null&&rightNode==null){
            return new Info(true,true);
        }else if(leftNode==null&&rightNode!=null){
            return new Info(false,false);
        }else if(leftNode!=null&&rightNode==null){
            return new Info(false,false);
        }else if(leftNode.val==rightNode.val){
            return new Info(false,false);
        }else{
            return new Info(false,true);
        }

        Info left = ans(leftNode.left,rightNode.left);
        Info right = ans(leftNode.right,rightNode.right);

        return new Info(left.isSameVal&&right.isSameVal,left.isSane&&right.isSane);

    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Info i = ans(p,q);
        return i.isSameVal&&i.isSane;

    }
    public int getMaxWidth (TreeNode root) {
        // write code here
        // write code here
        if(root==null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode,Integer> map = new HashMap<>();
        queue.offer(root);
        int cNode = 0;//当前层的节点数
        int max = 0;
        int levelNode = 1;//获取元素的层数
        int level = 1;//当前的层数
        map.put(root,1);
        while(!queue.isEmpty()){
            TreeNode head = queue.poll();
            levelNode = map.get(head);
            if(levelNode==level){
                cNode++;
            }else{
                max = Math.max(max,cNode);
                cNode = 1;
                level++;
            }
            if(head.left!=null){
                queue.offer(head.left);
                map.put(head.left,levelNode+1);
            }
            if(head.right!=null){
                queue.offer(head.right);
                map.put(head.right,levelNode+1);
            }
        }
        max = Math.max(cNode,max);
        return max;
    }



    public static int widthOfBinaryTree(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode,Integer> map = new HashMap<>();
        queue.offer(root);
        map.put(root,1);
        int cNode = 0;
        int max = 0;
        int clevel = 1;
        int levelNode = 1;
        while(!queue.isEmpty()){
            TreeNode head = queue.poll();
            levelNode = map.get(head);
            if(levelNode == clevel){
                cNode++;
            }else{
                max = Math.max(max,cNode);
                cNode = 1;
                clevel ++;
            }

            if(head.left!=null){
                queue.offer(head.left);
                map.put(head.right,levelNode+1);
            }

            if(head.right!=null){
                queue.offer(head.right);
                map.put(head.left,levelNode+1);
            }
        }
        max = Math.max(max,cNode);
        return max;

    }
    public static boolean  ans(TreeNode root){
        if(root==null){
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur = queue.poll();
        while(cur!=null){
            queue.offer(cur.left);
            queue.offer(cur.right);
            cur = queue.poll();
        }
        while(!queue.isEmpty()){
            if(queue.poll()!=null){
                return false;
            }
        }
        return true;

    }

    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if((p==null&&q!=null)||(p!=null&&q==null)){
            return false;
        }
        if(p.val!=q.val){
            return false;
        }
        return ans(isSameTree(p.left,q.left))&&(isSameTree(p.right,q.right));

    }
    public static boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==subRoot){
            return isSameTree(root,subRoot);
        }

        return (isSubtree(root.right,subRoot)||isSubtree(root.left,subRoot));


    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(3);
        head.right =new TreeNode(2);
        head.left.left = new TreeNode(5);
        head.left.right = new TreeNode(3);
        head.right.left = null;
        head.right.right = new TreeNode(9);
        isSubtree(head,head.left);

    }

}
